package com.lecode.array;

import org.omg.Messaging.SyncScopeHelper;

import java.lang.reflect.Array;
import java.util.*;

/**
 * 力扣
 * 
 * 数组
 * @author 韦朝
 *
 */
public class LecodeArray {

	/**
	 * 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
	 * 在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。
	 * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
	 * 
	 * 双指针法：
	 * 
	 * @param height
	 * @return
	 */
	public static int maxArea(int[] height) {
		if(height == null || height.length <=1) return 0;
        int left = 0; 
        int right = height.length - 1;
        //最大面积
        int area = 0;
		
        //当前面积
        int curr = 0;
        
		while(left < right){
			curr = getMinNum(height[left], height[right]) * (right - left);
			area = getMaxNum(area, curr);
			
			if(height[left] < height[right]){
				left++;
			}else{
				right--;
			}
		}
		
		return area;
    }

	/**
	 * 返回连个数的最大数
	 * @param area
	 * @param curr
	 * @return
	 */
	private static int getMaxNum(int area, int curr) {
		if(area > curr){
			return area;
		}else{
			return curr;
		}
	}

	/**
	 * 返回连个数的最小数
	 * @param i
	 * @param j
	 * @return
	 */
	private static int getMinNum(int i, int j) {
		
		if(i < j){
			return i;
		}else{
			return j;
		}
	}
	
	
	/**
	 * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，
	 * 使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组
	 * 
	 * 使用双指针的方法：
	 * @param nums
	 * @return
	 */
	public List<List<Integer>> threeSum(int[] nums) {
		if(nums == null || nums.length < 3) return null;
		//排序
		List<List<Integer>> ans = new ArrayList();
		Arrays.sort(nums);
		
		for(int i = 0; i < nums.length - 3; i++){
			
			if(nums[i] > 0) break;
			//当前数字等于上一个数字时，跳过
			if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
			
			int L = i + 1;
			int R = nums.length - 1;
			
			while(L < R){
				int sum = nums[i] + nums[L] + nums[R];
				if(sum == 0){
					ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
					
					while(L < R && nums[L] == nums[L + 1]) L++;
					while(L < R && nums[R] == nums[R - 1]) R++;
					
					L++;
					R--;
				}else if (sum > 0){
					R--;
				}else{
					L++;
				}
			}
		}
		
		return ans;
    }
	
	
	/**
	 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。
	 * 找出 nums 中的三个整数，使得它们的和与 target 最接近。
	 * 返回这三个数的和。假定每组输入只存在唯一答案。
	 * 双指针
	 * @param nums
	 * @param target
	 * @return
	 */
	public static int threeSumClosest(int[] nums, int target) {
        if(nums == null | nums.length < 3) return 0;
        
        //排序
        Arrays.sort(nums);
        
        //定义一个最大差值
        int distinct = Integer.MAX_VALUE;
        int res = nums[0] + nums[1] + nums[nums.length - 1];
        
        for(int i = 0; i < nums.length - 2; i++){
        	if (i > 0 && nums[i] == nums[i - 1]) {continue;}
        	
        	int left = i + 1;
        	int right = nums.length - 1;
        	
        	while(left < right){
        		int sum = nums[i] + nums[left] + nums[right];
        		
        		if(sum < target){
        			left++;
        		}else if(sum > target) {
        			right--;
        		}else if(sum == target) {
        			return sum;
        		}
        		
        		if(Math.abs(sum - target) < distinct){
        			distinct = Math.abs(sum - target);
        			res = sum;
        		}
        	}
        }
		return res;
    }
	
	
	
	/**
	 * 给定一个包含 n 个整数的数组 nums 和一个目标值 target，
	 * 判断 nums 中是否存在四个元素 a，b，c 和 d ，
	 * 使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
	 * @param nums
	 * @param target
	 * @return
	 */
	public static List<List<Integer>> fourSum(int[] nums, int target) {
		List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(nums ==null || nums.length < 4) return result;
        
        
        Arrays.sort(nums);
        int left = 0;
        int right = 0;
        int n = nums.length;
        
        for(int i = 0; i < nums.length - 3; i++){
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            if (nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;

            
        	for(int j = i + 1; j < nums.length -2; j++){
                if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
                if (nums[i] + nums[j] + nums[n - 1] + nums[n - 2] < target) continue;
                if(j - i > 1 && nums[j] == nums[j - 1]) continue;
                
        		left = j + 1;
            	right = nums.length - 1;
            	int pre = j;
            	while(left < right){
            		int sum = nums[i] + nums[pre] + nums[left] + nums[right];
            		
            		if(sum == target){
            			List<Integer> list = new ArrayList<Integer>();
            			list.add(nums[i]);
            			list.add(nums[pre]);
            			list.add(nums[left]);
            			list.add(nums[right]);
            			result.add(list);
            			
            			while(left < right && nums[left] == nums[left + 1]) ++left;
            			while(left < right && nums[right] == nums[right - 1]) --right;
            			
            			left++;
            			right--;
            		}else if(sum < target){
            			left++;
            		}else if(sum > target){
            			right--;
            		}
            		
            	}
        	}
        	
        }
        
        return result;
    }
	
	/**
	 * 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
	 *不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成
	 *快慢指针
	 * @param nums
	 * @return
	 */
	public static int removeDuplicates(int[] nums) {
		if (nums.length == 0) return 0;
		Arrays.sort(nums);
	    int i = 0;
	    for (int j = 1; j < nums.length; j++) {
	        if (nums[j] != nums[i]) {
	            i++;
	            nums[i] = nums[j];
	        }
	    }
	    return i + 1;
    }
	
	
	public static int removeDuplicates2(int[] nums) {
		if(nums == null || nums.length == 0) return 0;
		Arrays.sort(nums);
        int i = 0;
        for(int j = 1; j < nums.length; j++){
        	boolean flag = true;
        	for(int n = 0; n <= i; n++){
        		if(nums[j] == nums[n]){
        			flag = false;
        			break;
        		}
        	}
        	if(flag){
        		i++;
        		nums[i] = nums[j];
        	}
        }
		
		return i + 1;
    }
	
	/**
	 * 给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
	 *不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成
	 *
	 *双指针
	 * @param nums
	 * @param val
	 * @return
	 */
	public static int removeElement(int[] nums, int val) {
        
		int i = 0;
		for(int j = 0; j < nums.length; j++){
			if(nums[j] != val){
				nums[i] = nums[j];
				i++;
			}
		}
		return i;
    }
	
	
	/**
	 * 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
		( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
		搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
		你可以假设数组中不存在重复的元素。
	 * @param nums
	 * @param target
	 * @return
	 */
	public int search(int[] nums, int target) {
        
        for(int i = 0, j = nums.length - 1; i <= j; i++, j--){
            if(nums[i] == target){
                return i;
            }
            if(nums[j] == target){
                return j;
            }
        }
        
        return -1;
    }
	
	/**
	 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
		你的算法时间复杂度必须是 O(log n) 级别。
		如果数组中不存在目标值，返回 [-1, -1]。
	 *双指针法
	 * @param nums
	 * @param target
	 * @return
	 */
	public static int[] searchRange(int[] nums, int target) {
        int[] array = {-1, -1};
        for(int i = 0, j = nums.length - 1; i <= j; i++, j--){
            if(array[0] != -1 && array[1] != -1){
                break;
            }
            if(array[0] != -1){
                i--;
            }
            if(array[1] != -1){
                j++;
            }
            if(array[0] == -1 && nums[i] == target){
                array[0] = i;
                i--;
            }
            if(array[1] == -1 && nums[j] == target){
                array[1] = j;
                j++;
            }
        }
        return array;
    }
	
	/**
	 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
		你可以假设数组中无重复元素。
	 * @param nums
	 * @param target
	 * @return
	 */
	public int searchInsert(int[] nums, int target) {
		for(int i = 0; i < nums.length; i++){
			if(i != nums.length - 1 && nums[i] < target && target < nums[i + 1]){
				//插入元素
				return i + 1;
			}else if (nums[i] == target){
				return i;
			}else if (nums[i] > target){
                return i;
            }
		}
		
		return nums.length;
    }
	
	/**
	 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
		candidates 中的数字可以无限制重复被选取。
		说明：
		所有数字（包括 target）都是正整数。
		解集不能包含重复的组合。 
	 *回溯+剪枝算法
	 * @param candidates
	 * @param target
	 * @return
	 */
	public static List<List<Integer>> combinationSum(int[] candidates, int target) {
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		Arrays.sort(candidates);
		
        for(int i = 0; i < candidates.length; i++){
        	List<Integer> list = new ArrayList<Integer>();
        	list.add(candidates[i]);
        	findPrune(list, target - candidates[i], candidates, result);
        }
        return result;
    }
	
	
	public static void findPrune(List<Integer> list, int target, int [] nums, List<List<Integer>> result){
		if(target < 0) return;
		if(target == 0){
			result.add(list);
			return;
		}
		
		for(int i = 0; i < nums.length; i++){
			if(nums[i] > target) break;
			if(list.get(list.size() - 1) > nums[i])continue;
			
			List<Integer> copy = new ArrayList<Integer>();
			copy.addAll(list);
			copy.add(nums[i]);
			findPrune(copy, target - nums[i], nums, result);
		}
	}
	
	/**
	 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
		candidates 中的每个数字在每个组合中只能使用一次。
	 *回溯+剪枝算法
	 * @param candidates
	 * @param target
	 * @return
	 */
	public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		Arrays.sort(candidates);
		
        for(int i = 0; i < candidates.length; i++){
        	if(i != 0 && candidates[i] == candidates[i - 1]) continue;
        	List<Integer> list = new ArrayList<Integer>();
        	list.add(candidates[i]);
        	findPrune2(list, target - candidates[i], candidates, result, i);
        }
        return result;
    }
	
	
	public static void findPrune2(List<Integer> list, int target, int [] nums, List<List<Integer>> result, int current){
		if(target < 0) return;
		if(target == 0){
			if(!result.contains(list)){
				result.add(list);
			}
			return;
		}
		
		for(int i = current + 1; i < nums.length; i++){
			if(nums[i] > target) break;

			List<Integer> copy = new ArrayList<Integer>();
			copy.addAll(list);
			copy.add(nums[i]);
			findPrune2(copy, target - nums[i], nums, result, i);
		}
	}
	
	
	/**
	 * 给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
	 * 桶排序
	 * 将正确的数组放到正确的位置
	 * [3, 4, -1, 1]  例如： 3正确的位置是index = 2, 4的位置为index = 3....
	 * 一个萝卜一个坑，
	 * 
	 * 大于数组长度的和小于0的数字都是"废物数字"： 所以正确的数组顺序为[1, -1, 3, 4]
	 * 第一个不顺眼的数字为最小的正整数
	 * 
	 * @param nums
	 * @return
	 */
	public int firstMissingPositive(int[] nums) {
        
		for(int i = 0; i < nums.length; i++){
			//前两个条件判断该位置的数字是否为废物数字，后一个条件判断该位置是否为正确的数字
			while(nums[i] > 0 && nums[i] < nums.length && nums[nums[i] - 1] != nums[i]){
				//将当前位置的数组放到它该在的位置
				int temp = nums[i];
				nums[i] = nums[nums[i] - 1];
				nums[nums[i] - 1] = temp;
			}
		}
		
		for(int i = 0; i < nums.length; i++){
			if(nums[i] != i + 1){
				return i + 1;
			}
		}
		
		return nums.length + 1;
    }
	
	/**
	 * 力扣：20
	 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
		有效字符串需满足：
		左括号必须用相同类型的右括号闭合。
		左括号必须以正确的顺序闭合。
	 * @param s
	 * @return
	 */
    public static boolean isValid(String s) {
        if(s == null) return true;
    	Map<Character, Character> map = new HashMap<Character, Character>();
    	map.put('}', '{');
    	map.put(')', '(');
    	map.put(']', '[');
        
    	//存放左括号
    	Stack<Character> list = new Stack<Character>();
    	
    	for(int i = 0; i < s.length(); i++){
    		//遇到右括号的逻辑
    		if(map.containsKey(s.charAt(i))){
    			if(list.size() == 0) return false;
    			Character info = list.pop();
    			if(map.get(s.charAt(i)).equals(info))
    				continue;
    			
    			return false;
    		}else{
    			//遇到做括号的逻辑
    			list.push(s.charAt(i));
    		}
    	}
    	if(list.size() == 0){
    		return true;
    	}
    	
    	return false;
    }
	
    /**
     * 22、括号的生成
     * 
     * 给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
     * 
     * 有效括号的数量
     * @param n
     * @return
     */
    public static List<String> generateParenthesis(int n) {
        if(n == 0) return null;
    	List<String> list = new ArrayList<String>();
    	
    	String s = "(";
    	int left = n - 1;
    	int right = n;
    	process(left, right, s, list);
    	
    	return list;
    }
    
    public static void process(int left, int right, String s, List<String> list) {
		if(left == 0 && right == 0){
			list.add(s);
			return;
		}
		
		//左括号不等于0时就可以加
		if(left > 0){
			process(left - 1, right, s + "(", list);
		}
		
		//右括号的剩余数量多于左括号时才能加
		if(left < right){
			process(left, right - 1, s + ")", list);
		}
	}

    /**
     * 28、实现 strStr()
     * 给定一个 haystack 字符串和一个 needle 字符串，
     * 在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
     * 
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr(String haystack, String needle) {
        if(needle == null || needle.equals("")) return 0;
        if(haystack == null || haystack.equals("")) return -1;
        
        int num = 0;
        for(int i = 0; i < haystack.length(); i++){
        	num = 0;
        	for(int j = 0; j< needle.length(); j++){
        		if(haystack.length() - i >= needle.length()){
        			if(haystack.charAt(i + j) == needle.charAt(j)){
        				num++;
        				continue;
        			}
        			break;
        		}else{
        			return -1;
        		}
        	}
        	if(num == needle.length()) return i;
        }
    	return -1;
    }
    
    /**
     * 30. 串联所有单词的子串
     * 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
	 *	注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
	 *
	 *滑窗算法
     * @param s
     * @param words
     * @return
     */
    public static List<Integer> findSubstring(String s, String[] words) {
    	List<Integer> list = new ArrayList<Integer>();
    	
        if(s == null || s.equals("") || words == null || words.length == 0) return list;
        
        //窗口长度
        int length = words[0].length() * words.length;
    	
        for(int i = 0; i < s.length(); i++){
        	if((i + length) <= s.length()){
        		String temp = s.substring(i, i + length);
        		boolean flag = compare(temp, words);
        		if(flag) list.add(i);
        	}else{
        		break;
        	}
        }
    	return list;
    }
    
	public static boolean compare(String temp, String[] words) {
		List<String> wordsList = Arrays.asList(words);
		List<String> arrList = new ArrayList<String>(wordsList);
		
		for(int i = 0; i < temp.length(); i = i + words[0].length()){
			String str = temp.substring(i, i + words[0].length());
			if(!arrList.contains(str)){
				return false;
			}else{
				for (int j = 0; j < arrList.size(); j++) {
					if(str.equals(arrList.get(j))){
						arrList.remove(j);
						break;
					}
				}
			}
		}
		return true;
	}

	/**
	 * 38. 报数
	 * 
	 * 
	 * 
	 * 
	 * @param n
	 */
	public static String countAndSay(int n) {
        if(n == 0 || n < 0) return "";
        
        List<String> info = new ArrayList<String>();
        info.add("1");
        
        int num = 1;
        
		return process(num + 1, info, n).replace("[", "").replace("]", "").replace(", ", "");
    }
	
	public static String process(int num, List<String> info, int n) {
		if(num > n) return info.toString();
		List<String> message = new ArrayList<String>();
		
		for(int i = 0, j = 0; i < info.size();){
			if(j >= info.size()){
				message.add(j - i + "");
				message.add(info.get(i));
				break;
			}
			if(info.get(i).equals(info.get(j))){
				j++;
			}else{
				message.add(j - i + "");
				message.add(info.get(i));
				i = j; 
				j++;
			}
		}
		
		return process(num + 1, message, n);
	}

	
	/**
	 * 46:全排列
	 * 
	 * 使用递归 
	 * @param nums
	 * @return
	 */
	public static List<List<Integer>> permute(int[] nums) {
		
		List<List<Integer>> output = new LinkedList<List<Integer>>();
		
		ArrayList<Integer> nums_lst = new ArrayList<Integer>();
	    for (int num : nums)
	      nums_lst.add(num);
	    
	    int n = nums.length;
	    backtrack(n, nums_lst, output, 0);
	    return output;
	} 
	
	/**
	 * 
	 * @param n
	 * @param nums_lst
	 * @param output
	 * @param demp    每一次递归固定一个数字   demp为固定数字的数量
	 */
	public static void backtrack(int n, ArrayList<Integer> nums_lst, List<List<Integer>> output, int demp) {
		if(demp >= n){
			output.add(new ArrayList<Integer>(nums_lst));
		}else{
			for(int i = demp; i < n; i++){
				Collections.swap(nums_lst, i, demp);
				backtrack(n, nums_lst, output, demp + 1);
				
				//恢复原数组的位置
				Collections.swap(nums_lst, i, demp);
			}
		}
	}

	
	/**
	 * 45:跳跃游戏
	 * 
	 * 我们每次在可跳范围内选择可以使得跳的更远的位置
	 * 
	 * 贪心算法，每次找局部最优，最后达到全局最优，完美
	 * @param nums
	 * @return
	 */
    public int jump(int[] nums) {
        int end = 0;
        int maxPosition = 0;
        int step = 0;
        for(int i = 0; i < nums.length - 1; i++){
        	//记录沿途的最大跳跃位置
        	maxPosition = Math.max(maxPosition, nums[i] + i);
        	//当到达边界时，更新步数
        	if(i == end){
        		end = maxPosition;
        		step++;
        	}
        }
        return step;
    }


	/**
	 * 48、旋转图像
	 * 给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。
	 *
	 * 先转置  后翻转
	 * 转置：行变列    列表行
	 * 翻转：第一列和最后一列交换    依次交换
	 * @param num
	 */
	public static void rotate(int[][] num) {
		int length = num.length;
		//转置
		for (int i = 0; i < length; i++){
			for (int j = i; j < length; j++){
				int temp = num[j][i];
				num[j][i] = num[i][j];
				num[i][j] = temp;
			}
		}

		//翻转 (列翻转一半)
		for (int i = 0; i < length; i++){
			for (int j = 0; j < length / 2; j++){
				int temp = num[i][j];
				num[i][j] = num[i][length - 1 - j];
				num[i][length - 1 - j] = temp;
			}
		}
	}

	/**
	 * 49. 字母异位词分组
	 *给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
	 *
	 * 对每一个自字符串拆成字符数组，进行排序
	 *
	 *
	 * @param strs
	 * @return
	 */
	public static List<List<String>> groupAnagrams(String[] strs) {
		if (strs.length == 0) return null;
		Map<String, List<String>> map = new HashMap();
		for (String s: strs){
			char[] chars = s.toCharArray();
			//将字符进行排序
			Arrays.sort(chars);
			String key = String.valueOf(chars);
			if (!map.containsKey(key)) map.put(key, new ArrayList<String>());

			//将排序相同的字符串放到同一个list中
			map.get(key).add(s);
		}
		return new ArrayList<List<String>>(map.values());
	}

	/**
	 * 50. Pow(x, n)
	 * 计算 x 的 n 次幂函数。
	 * n可能为负数
	 * @param x
	 * @param n
	 * @return
	 */
	public static double myPow(double x, int n) {
		if (x == 1) return x;
		long N = n;
		if (n < 0){
			x = 1 / x;
			N = -N;
		}
		double result = 1;
		for (long i = 0; i < N; i++){
			result  = result * x;
		}
		return result;
	}

	/**
	 * 方法2:
	 *
	 * 递归求n的一半次方
	 * @param x
	 * @param n
	 * @return
	 */
	public static double myPow2(double x, int n) {
		if (x == 1) return x;
		long N = n;
		if (n < 0){
			x = 1 / x;
			N = -N;
		}
		return fastPow(x, N);
	}

	/**
	 * 递归求 n的一半次方
	 * 偶数和奇数次方
	 *
	 * @param x
	 * @param n
	 * @return
	 */
	private static double fastPow(double x, long n) {
		if (n == 0) return 1.0;
		//求一半的结果
		double half = fastPow(x, n / 2);
		if (n % 2 == 0) {
			return half * half;
		} else {
			return half * half * x;
		}
	}

	/**
	 * 51. N皇后
	 * n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击
	 * @param n
	 * @return
	 */
	public List<List<String>> solveNQueens(int n) {


		return null;
	}


	/**53. 最大子序和
	 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
	 *
	 * 动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
	 如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
	 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
	 每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果
	 * @param nums
	 * @return
     */
	public int maxSubArray(int[] nums) {
		int ans = nums[0];
		int sum = 0;
		for (int num: nums){
			if (sum > 0){
				sum += num;
			}else {
				sum = num;
			}
			ans = Math.max(sum, ans);
		}
		return ans;
	}

	/**
	 *给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
	 * 输入:
		 [
			 [ 1, 2, 3 ],
			 [ 4, 5, 6 ],
			 [ 7, 8, 9 ]
		 ]
	 输出: [1,2,3,6,9,8,7,4,5]
			 0.用坐标x、y表示当前遍历的位置
			 1.用一个pos变量指示当前行进方向（左、右、上、下）
			 2.用四个变量bLeft、bRight、bTop、bBottom实时记录当前的上、下、左、右边界，以便遍历到边界时及时修正路线！
			 3.分别初始化边界值，每当当前遍历到越过一条边界时，对坐标x和y的值进行修正，同时还需修改pos（改变遍历的方向）
			 4.修改边界值（原因是这一层已经遍历过了边界值，下一次的边界值就不包括这个值了！）
	 * @param matrix
	 * @return
     */
	public List<Integer> spiralOrder(int[][] matrix) {
		if(matrix==null)
			return null;
		if(matrix.length==0)
			return new ArrayList<Integer>();

		int x=0,y=0;
		int pos = 1;//指示前进方向,1表示向右，2表示向下，3表示向左，4表示向上
		int bLeft = 0;//左边界
		int bRight=  matrix[0].length - 1;//右边界
		int bTop = 1;//上边界
		int bBottom = matrix.length - 1;//下边界

		int size = matrix.length * matrix[0].length;
		List<Integer> resList = new ArrayList<Integer>();
		for(int i=0;i<size;i++)
		{
			resList.add(matrix[x][y]);
			switch(pos)
			{
				case 1:
					y++;
					if(y>bRight)
					{
						//越过右边界
						y = bRight;
						x++;
						bRight--;
						pos = 2;
					}
					break;

				case 2:
					x++;
					if(x>bBottom)
					{
						//越过下边界
						x = bBottom;
						y--;
						bBottom--;
						pos = 3;
					}
					break;

				case 3:
					y--;
					if(y<bLeft)
					{
						//越过左边界
						y = bLeft;
						x--;
						bLeft++;
						pos=4;
					}
					break;

				case 4:
					x--;
					if(x<bTop)
					{
						//越过上边界
						x = bTop;
						y++;
						bTop++;
						pos = 1;
					}
					break;
			}
		}
		return resList;
	}

	/**
	 * 给定一个非负整数数组，你最初位于数组的第一个位置。
	 数组中的每个元素代表你在该位置可以跳跃的最大长度。
	 判断你是否能够到达最后一个位置。
	 输入: [2,3,1,1,4]
	 输出: true
	 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
	 * @param nums
	 * @return
     */
	public boolean canJumpOvertime(int[] nums) {
		//递归：会超时，计算所有可能性
		if(nums==null || nums.length==0) {
			return true;
		}
		return dfs(0,nums);
	}

	public boolean dfs(int index, int[] nums){
		if (index >= nums.length - 1){
			return true;
		}
		for (int n = 1; n<= nums[index]; n++){
			if (dfs(n+index, nums)){
				return true;
			}
		}
		return false;
	}

	public boolean canJump(int[] nums) {
		if (nums == null || nums.length == 0){
			return true;
		}

		int length = nums.length;
		int ans = 0;
		for (int i = 0; i < nums.length; i++){
			if (ans >= i){
				ans = Math.max(ans, i + nums[i]);
			}
		}

		if (ans >= length){
			return true;
		}
		return false;
	}

	/**
	 * 56. 合并区间
	 * 给出一个区间的集合，请合并所有重叠的区间。
	 * @param intervals
	 * @return
     */
	public int[][] merge(int[][] intervals) {
		int len = intervals.length;
		if (len < 1) return intervals;
		int row = intervals[0].length;

		//排序
		//Arrays.parallelSort(intervals, Comparator.comparingInt(x -> x[0]));

		List<int[]> list = new ArrayList<int[]>();
		for (int i = 0; i < len - 1; i++) {
			if (intervals[i][row - 1] >= intervals[i + 1][0]) {
				intervals[i + 1][0] = intervals[i][0];
				intervals[i + 1][row - 1] = Math.max(intervals[i + 1][row - 1], intervals[i][row - 1]);
			} else {
				list.add(intervals[i]);
			}
		}

		list.add(intervals[len - 1]);
		return list.toArray(new int[list.size()][row]);
	}


	/**
	 * 57. 插入区间
	 * @param intervals
	 * @param newInterval
     * @return
     */
	public int[][] insert(int[][] intervals, int[] newInterval) {


		return null;
	}


	/**
	 * 58. 最后一个单词的长度
	 * @param s
	 * @return
     */
	public static int lengthOfLastWord(String s) {
		if(s == null) return 0;
		s = s.trim();
		int sum = 0;
		for (int i = s.length() - 1; i >=0; i--){
			if (s.charAt(i) != ' '){
				sum++;
			}else {
				break;
			}
		}
		return sum;
	}

	/**
	 * 59. 螺旋矩阵 II
	 * @param n
	 * @return
     */
	public static int[][] generateMatrix(int n) {
		int[][] result = new int[n][n];
		int pox = 1;  //1、左   2、下   3、右  4、上
		int leftMax = n - 1;
		int downMax = n - 1;
		int rightMin = 0;
		int UpMin = 1;

		int row = 0;  int clum = 0;
		int num = 1;
		while(num <= n * n){
			switch (pox){
				case 1:
					if (clum <= leftMax){
						result[row][clum] = num++;
						clum++;
					}else {
						pox = 2;
						leftMax = leftMax - 1;
						clum--;
						row++;
					}
					break;
				case 2:
					if (row <= downMax){
						result[row][clum] = num++;
						row++;
					}else {
						pox = 3;
						downMax = downMax - 1;
						row--;
						clum--;
					}
					break;
				case 3:
					if (clum >= rightMin){
						result[row][clum] = num++;
						clum--;
					}else {
						pox = 4;
						rightMin = rightMin + 1;
						clum++;
						row--;
					}
					break;
				case 4:
					if (row >= UpMin){
						result[row][clum] = num++;
						row--;
					}else {
						pox = 1;
						UpMin = UpMin + 1;
						row++;
						clum++;
					}
					break;
			}
		}
		return result;
	}

	/**
	 * 60. 第k个排列
	 * @param n
	 * @param k
     * @return
     */
	public String getPermutation(int n, int k) {
		int[] nums = new int[n];
		for (int i = 0; i < n; i++) nums[i] = i + 1;
		boolean[] used = new boolean[n];//记录当前的索引的数是否被使用过
		return dfs(nums, new ArrayList<String>(), used, 0, n, k);
	}

	public String dfs(int[] nums, List<String>list, boolean[] used, int depth, int n, int k){
		if (depth == n){
			StringBuffer result = new StringBuffer();
			for (String a: list){
				result.append(a);
			}
			return result.toString();
		}
		//计算当前深度的数量
		int cur = factorial(n - depth - 1);
		for (int i = 0; i < n; i++){
			if (used[i]) continue;
			if (cur < k){
				k -= cur;
				continue;
			}
			used[i] = true;
			list.add(nums[i] + "");
			return dfs(nums, list, used, depth + 1, n, k);
		}
		return null;
	}

	private int factorial(int n) {
		int res = 1;
		while (n > 0) {
			res *= n--;
		}
		return res;
	}

	/**
	 * 62、不同路径
	 * 递归
	 * @param m
	 * @param n
     * @return
     */
	public static int uniquePaths(int m, int n) {
		int[][] record = new int[m][n];
		for (int i = 0; i < m; i++) record[i][0] = 1;
		for (int i = 0; i < n; i++) record[0][i] = 1;
		for (int i = 1; i < m; i++){
			for (int j = 1; j < n; j++){
				record[i][j] = record[i - 1][j] + record[i][j];
			}
		}
		return record[m - 1][n - 1];
	}

	/**
	 * 62：不同路径
	 * @param obstacleGrid
	 * @return
     */
	public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
		int m = obstacleGrid.length;
		int n = obstacleGrid[0].length;

		int[][] record = new int[m + 1][n + 1];
		for (int i = 0; i < m; i++){
			for (int j = 0; j < n; j++){
				if(obstacleGrid[i][j]==1) continue;
				if (i == 0 &&  j== 0) record[i][j] = 1;
				else if(i == 0) record[i][j] = record[i][j - 1];
				else if(j == 0) record[i][j] = record[i - 1][j];
				else record[i][j] = record[i - 1][j] + record[i][j - 1];

			}
		}
		return record[m - 1][n - 1];
	}

	/**
	 * 64、最短路径和
	 *
	 * 动态规划
	 * @param grid
	 * @return
     */
	public int minPathSum(int[][] grid) {
		for (int i = 0; i < grid.length; i++){
			for (int j = 0; j < grid[0].length; j++){
				if (i == 0 && j == 0) continue;
				if (i == 0) grid[i][j] = grid[i][j - 1] + grid[i][j];
				else if (j == 0) grid[i][j] = grid[i - 1][j] + grid[i][j];
				else grid[i][j] = Math.min(grid[i][j - 1], grid[i - 1][j])  + grid[i][j];
			}
		}
		return grid[grid.length][grid[0].length];
	}

	/**
	 * 66、加一
	 * @param digits
	 * @return
     */
	public int[] plusOne(int[] digits) {
		for (int i = digits.length - 1; i <= 0; i--){
			digits[i]++;
			digits[i] = digits[i] % 10;
			if (digits[i] != 0) return digits;
		}
		digits = new int[digits.length + 1];
		digits[0] = 1;
		return digits;
	}

	/**
	 * 67、二进制求和
	 * @param a
	 * @param b
     * @return
     */
	public static String addBinary(String a, String b) {
		int ca = 0;
		StringBuffer result = new StringBuffer();
		for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i --, j--){
			int sum = ca;
			sum += (i >= 0 ? a.charAt(i) - '0':0);
			sum += (j >= 0 ? b.charAt(j) - '0': 0);
			result.append(sum % 2);
			ca = sum / 2;
		}
		result.append(ca == 1 ? ca : "");
		return result.reverse().toString();
	}

	/**
	 * 69. x 的平方根
	 *
	 * 二分查找
	 * @param x
	 * @return
     */
	public int mySqrt(int x) {
		int l = 0, r = x, ans = 0;
		while (l <= r){
			int min = (l + r) / 2;

			if (min * min <= x){
				ans = min;
				l = min + 1;
			}else {
				r = min - 1;
			}

		}
		return ans;
	}

	/**
	 * 70. 爬楼梯
	 *
	 * 动态规划
	 * d[n] = d[n - 1] + d[n - 1]
	 * 本问题其实常规解法可以分成多个子问题，爬第n阶楼梯的方法数量，等于 2 部分之和
	 爬上 n−1 阶楼梯的方法数量。因为再爬1阶就能到第n阶
	 爬上 n−2 阶楼梯的方法数量，因为再爬2阶就能到第n阶
	 * @param n
	 * @return
     */
	public int climbStairs(int n) {
		int dp[] = new int[n + 1];
		dp[0] = 1;
		dp[1] = 1;
		for (int i = 2; i<= n; i++){
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		return dp[n];
	}

	/**
	 * 72、编辑距离(用于求字符串的相似度)
	 *
	 * 动态规划(求状态转移方程)
	 * 情况 1：word1[i] == word2[j]
	 如果 word1[i] == word2[j] 成立，则将 word1[0, i) 转换成为 word2[0, j) 的方案数就等于 将 word1[0, i - 1) 转换成为 word2[0, j - 1) 的方案数，即：

	 dp[i + 1][j + 1] = dp[i][j]；

	 情况 2：word1[i] != word2[j]
	 如果 word1[i] != word2[j] ，则将 word1[0, i) 转换成为 word2[0, j) 的方案数就等于下面 3
	 种情况的最少操作数（「最优子结构」）：

	 (对一个字符串的操作有三种操作：删除、插入、替换)
	 考虑修改 word1[i] 成为 word2[j]；
	 此时 dp[i + 1][j + 1] = dp[i][j] + 1，这里的 1 代表了将 word1[i] 替换成为 word2[j] 这一步操作。

	 (删除)考虑将 word1[0, i] 的最后一个字符删除；
	 此时 word1[0, i - 1] 到 word2[0, j] 的最少操作数 + 1+1，就是这种方案数的最少操作数，即： dp[i + 1][j + 1] = dp[i][j + 1] + 1，这里的 1 代表了 word1[0, i] 的最后一个字符删除这一步操作。

	 (插入)考虑将 word1[0, i] 的末尾添加一个字符使得 word1[i + 1] == word2[j]；
	 此时考虑方案的时候，由于 word1[i + 1] == word2[j]，状态转移就不应该考虑 word2[j]，因此 word1[0, i] 到 word2[0, j - 1] 的最少操作数 + 1+1，就是这种方案数的最少操作数，即： dp[i + 1][j + 1] = dp[i + 1][j] + 1，这里的 1 代表了将 word1[0, i] 的末尾添加一个字符使得 word1[i + 1] == word2[j]。（注意：可以考虑一下为什么得先讨论 word1[i] == word2[j] 的情况。）

	 在这 3 种操作中取最小值。
	 dp[i + 1][j + 1] = min(dp[i][j], dp[i][j + 1], dp[i + 1][j]) + 1
     */
	public int minDistance(String word1, String word2) {
		int n1 = word1.length(); //行
		int n2 = word2.length(); //列
		int[][] dp = new int[n1 + 1][n2 + 1];
		for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;
		for (int j = 1; j <= n2; j++) dp[0][j] = dp[0][j - 1] + 1;

		for (int i = 1; i <= n1; i++){
			for (int j = 1; j <= n2; j++){
				if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
				else {
					dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
				}
			}
		}
		return dp[n1][n2];
	}

	/**
	 * 73. 矩阵置零
	 * 给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
	 * @param matrix
     */
	public void setZeroes(int[][] matrix) {
		Set<Integer> row = new HashSet<Integer>();
		Set<Integer> clu = new HashSet<Integer>();

		for (int i = 0; i < matrix.length; i++){
			for (int j = 0; j < matrix[0].length; j++){
				if (matrix[i][j] == 0){
					row.add(i);
					clu.add(j);
				}
			}
		}
		for (int i = 0; i < matrix.length; i++){
			for (int j = 0; j > matrix[0].length; j++){
				if (row.contains(i) && clu.contains(j)){
					matrix[i][j] = 0;
				}
			}
		}
	}

	/**
	 * 74. 搜索二维矩阵
	 *
	 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
		 每行中的整数从左到右按升序排列。
		 每行的第一个整数大于前一行的最后一个整数。
	 *
	 * 二分查找
	 * @param matrix
	 * @param target
     * @return
     */
	public boolean searchMatrix(int[][] matrix, int target) {
		int m = matrix.length;
		if (m == 0) return false;
		int n = matrix[0].length;

		int left = 0;
		int right = m * n - 1;
		int currentIndex, currentValue;
		while (left <= right){
			currentIndex = (left + right) / 2;
			currentValue = matrix[currentIndex / n][currentIndex % n];
			if (currentValue == target) return true;
			else if (target < currentValue){
				right = currentIndex - 1;
			}else {
				left = currentIndex + 1;
			}
		}
		return false;
	}

	/**
	 * 75. 颜色分类
	 *
	 * 原地对数组进行排序:冒泡算法
	 * @param nums
     */
	public static void sortColors(int[] nums) {
		if (nums == null) return;
		for (int i = 0; i < nums.length; i++){
			for (int j = 1; j < nums.length - i; j++){
				if (nums[j - 1] > nums[j]){
					int temp = nums[j];
					nums[j] = nums[j - 1];
					nums[j - 1] = temp;
				}
			}
		}
	}


	/**
	 * 76. 最小覆盖子串
	 *
	 * 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
	 * @param s
	 * @param t
     * @return
     */
	Map<Character, Integer> ori = new HashMap<Character, Integer>();
	Map<Character, Integer> cur = new HashMap<Character, Integer>();
	public String minWindow(String s, String t) {
		int tLength = t.length();
		for (int i = 0; i < tLength; i++){
			ori.put(t.charAt(i), ori.getOrDefault(t.charAt(i), 0) + 1);
		}
		int l = 0, r = -1;
		int len = Integer.MAX_VALUE;
		int ansL = -1, ansR = -1;
		while (r <= s.length()){
			++r;
			if (ori.containsKey(s.charAt(r))){
				cur.put(s.charAt(r), cur.getOrDefault(s.charAt(r), 0) + 1);
			}
			while (check() && l <= r){
				if ((r - l + 1) < len){
					len = r - l + 1;
					ansL = l;
					ansR = l + len;
				}
				if (ori.containsKey(s.charAt(l))){
					cur.put(s.charAt(l), cur.getOrDefault(s.charAt(l), 0) - 1);
				}
				++l;
			}
		}
		return ansL == -1? "":s.substring(ansL, ansR);
	}

	/**
	 * 判断滑窗是否符合条件
	 * @return
     */
	public boolean check(){
		Iterator iter = ori.entrySet().iterator();
		while (iter.hasNext()){
			Map.Entry entry = (Map.Entry) iter.next();
			Character c = (Character) entry.getKey();
			Integer val = (Integer) entry.getValue();
			if (cur.getOrDefault(c, 0) < val){
				return false;
			}
		}
		return true;
	}


	/**
	 * 77、组合
	 * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
	 * @param n
	 * @param k
     * @return
     */
	public List<List<Integer>> combine(int n, int k) {
		List<List<Integer>> out = new ArrayList<List<Integer>>();
		LinkedList<Integer> curr = new LinkedList<Integer>();
		backtrack(out, n, k, curr, 1);
		return out;
	}

	public void backtrack(List<List<Integer>> out, int n, int k, LinkedList<Integer>curr, int first){
		if (curr.size() == k){
			out.add(new LinkedList<Integer>(curr));
		}
		for (int i = first; i < n + 1; i++){
			curr.add(i);
			backtrack(out, n, k, curr, i + 1);
			curr.removeLast();
		}
		return;
	}

	/**
	 * 78. 子集
	 * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）
	 *
	 * 回溯法
	 * @param nums
	 * @return
     */
	public List<List<Integer>> subsets(int[] nums) {
		List<List<Integer>> out = new ArrayList<List<Integer>>();
		LinkedList<Integer> curr = new LinkedList<Integer>();
		backtrackTwo(out, nums, 0, curr);
		out.add(new LinkedList<Integer>());
		return out;
	}

	public void backtrackTwo(List<List<Integer>> out, int[] nums, int first,  LinkedList<Integer>curr){
		for (int i = first; i < nums.length; i++){
			curr.add(nums[i]);
			out.add(new LinkedList<Integer>(curr));
			backtrackTwo(out, nums, i + 1, curr);
			curr.removeLast();
		}
		return;
	}


	/**
	 * 79. 单词搜索
	 *
	 * 回溯
	 * @param board
	 * @param word
     * @return
     */
	static int row, clum;
	static boolean hasExist = false;
	//定义方向
	private static int[][] dires = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
	//定义字母是否使用
	private static boolean[][] visited;
	public static boolean exist(char[][] board, String word) {
		int row = board.length;
		if (row == 0) return false;
		int clum = board[0].length;
		if (row * clum < word.length()){
			return false;
		}
		visited = new boolean[row][clum];
		char[] chars = word.toCharArray();
		for (int i = 0; i < row; i++){
			for (int j = 0; j < clum; j++){
				if (board[i][j] == chars[0]){
					backtraceExist(board, word, 1, i, j);
				}
				if (hasExist) return hasExist;
			}
		}
		return hasExist;
	}

	public static void backtraceExist(char[][] board, String word, int currIndex, int i, int j){
		if (hasExist){
			return;
		}
		if (currIndex == word.length()){
			hasExist = true;
			return;
		}
		visited[i][j] = true;
		for (int[] dire: dires){
			int newRow = dire[0] + i;
			int newClum = dire[1] + j;

			if (isIn(newRow, newClum) && !visited[newRow][newClum]
					&& board[newRow][newClum] == word.charAt(currIndex)){
				backtraceExist(board, word, currIndex + 1, newRow, newClum);
			}
		}
		visited[i][j] = false;
	}

	private static boolean isIn(int x, int y){
		return x >= 0 && x < row && y >= 0 && y < clum;
	}

	/**
	 *80. 删除排序数组中的重复项 II
	 *
	 * 快慢指正(三个指针)
	 *
	 * 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
	 * @param nums
	 * @return
     */
	public int removeDuplicates80(int[] nums) {
		if (nums == null) return 0;
		if(nums.length < 3 && nums.length >=2){
			return 2;
		}else if (nums.length == 1){
			return 1;
		}
		int a = 0, b = 1;
		for (int j = 2; j < nums.length; j++){
			if (!(nums[a] == nums[b] && nums[b] == nums[j])){
				a++;
				b++;
				nums[b] = nums[j];
			}
		}
		return b + 1;
	}

	/**
	 * 求最大回文串
	 * @return
     */
	public static String getMaxString(String s){
		String result = "";
		for (int i = 0; i < s.length(); i++){
			String s1 = checkString(s, i, i);
			String s2 = checkString(s, i, i + 1);
			result = s1.length() > result.length()? s1:result;
			result = s2.length() > result.length()? s2:result;
		}
		return result;
	}

	/**
	 * 求以当前字符为中心的最大回文串
	 */
	public static String checkString(String s, int l, int r){
		while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
			l--;
			r++;
		}
		return s.substring(l + 1, r);
	}

	/**
	 * 反转int类型的值，不能借用String
	 */
	public static int reverseInt(int n){
		int res = 0;
		while(n != 0){
			if (n % 10 == 0 && res == 0){
				n = n / 10;
				continue;
			}
			res = res * 10 + n % 10;
			n = n / 10;
		}
		return res;
	}

	public static void main(String[] args) {
		/*char[][] a = new char[][]{{'A','B','C','E'}, {'S','F','C','S'}, {'A','D','E','E'}};
		exist(a, "ABCCED");*/
		System.out.print(reverseInt(1909));
	}
}
